package com.dubious.interview.euler;

import java.util.ArrayList;
import java.util.List;

public class Problem26 {

    public static int run(int limit)
    {
        int maxRecurrenceSize = 0;
        int valueWithMaxRecurrenceSize = 0;
        for(int i = 1; i <= limit; i++)
        {
            int recurrenceSize = recurrenceSize(i);
            if(recurrenceSize > maxRecurrenceSize)
            {
                maxRecurrenceSize = recurrenceSize;
                valueWithMaxRecurrenceSize = i;
            }
        }
        
        return valueWithMaxRecurrenceSize;
    }
    
    private static int recurrenceSize(int base)
    {
        // the idea is to mimic the long-form division algorithm to find the recurrence
        
        // from http://en.wikipedia.org/wiki/Repeating_decimal, we know the following:
        //     - every rational number either terminates with a 0 or has a recurrence
        //     - we can determine the length of the recurrence by mimic'ing the long form 
        //       division algorithm
        
        // the algorithm works by analyzing the remainder at each step of the long division
        // if a remainder of 0 is found then we have no recurrence
        // if the same remainder is found a 2nd time then we can use the number of steps 
        // between the duplicated remainder to determine recurrence size
        
        // the number we are interested in is 1/i
        // this simplifies the algorithm even further as we know that subsequent steps in the 
        // long division algorithm will divide the remainder*10
        
        /*
         * To illustrate, here are some exampels:
         * d = 5
         * 1 / 5
         *     1. 1 / 5 gives remainder of 1
         *     2. 10 / 5 gives remainder of 0
         * THERE IS NO RECURRENCE for d = 5
         * 
         * d = 7
         * 1 / 7
         *     1. 1 / 7 gives remainder of 1
         *     2. 10 / 7 gives remainder of 3
         *     3. 30 / 7 gives remainder of 2
         *     4. 20 / 7 gives remainder of 6
         *     5. 60 / 7 gives remainder of 4
         *     6. 40 / 7 gives remainder of 5
         *     7. 50 / 7 gives remainder of 1
         * RECURRENCE for d = 7 has length 7 - 1 = 6
         * 
         * d = 6
         * 1 / 6
         *     1. 1 / 6 gives remainder of 1
         *     2. 10 / 6 gives remainder of 4
         *     3. 60 / 6 gives remainder of 4
         * RECURRENCE for d = 6 has length 3 - 2 = 1
         */
        
        int step = 1;
        int remainder = 1;
        List<Integer> remainders = new ArrayList<Integer>(base);
        while(remainder != 0)
        {
            step++;
            remainder = (remainder * 10) % base;
            // search whether this remainder already exists
            for(int i = 0; i < remainders.size(); i++)
            {
                if(remainders.get(i).equals(Integer.valueOf(remainder)))
                {
                    return step - i;
                }
            }
            
            remainders.add(Integer.valueOf(remainder));
        }
        
        // remainder of 0 means there is no recurrence
        return 0;
        
    }
}
